{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'myope': 'no lenses', 'hyper': 'soft'}}, 'young': 'soft'}}, 'yes': {'prescript': {'myope': 'hard', 'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}}}}}, 'reduced': 'no lenses'}}\n"
     ]
    }
   ],
   "source": [
    "import operator\n",
    "from math import log\n",
    "from collections import Counter\n",
    "\n",
    "#计算给定数据集的熵\n",
    "def calcShannonEnt(dataSet):   #dataset是数据集\n",
    "    numEntries = len(dataSet)  #计算数据集的长度\n",
    "\n",
    "    labelCounts = {}\n",
    "    for featVec in dataSet:    #计算分类标签label出现的次数\n",
    "        currentLabel = featVec[-1]    #每一行最后一个数据是标签，存储当前的标签\n",
    "        if currentLabel not in labelCounts.keys(): #为所有可能的分类创建字典，如果不在字典中，则创建键值\n",
    "            labelCounts[currentLabel] = 0\n",
    "        labelCounts[currentLabel] += 1\n",
    "\n",
    "    shannonEnt = 0.0  #熵初始值\n",
    "    for key in labelCounts:\n",
    "        prob = float(labelCounts[key])/numEntries #计算类别出现的概率\n",
    "        shannonEnt -= prob * log(prob,2) #计算熵，以2为底\n",
    "    return shannonEnt\n",
    "\n",
    "def splitDataSet(dataSet,index,value): #通过遍历dataset数据集，求出index对应的列的值为value的行\n",
    "    retDataSet = []\n",
    "    for featVec in dataSet:\n",
    "        if featVec[index] == value: #判断index列的值是否等于value\n",
    "            reducedFeatVec = featVec[:index] #取前index行\n",
    "            reducedFeatVec.extend(featVec[index+1:]) #跳过index行，取后面的数据\n",
    "            retDataSet.append(reducedFeatVec) \n",
    "    return retDataSet\n",
    "\n",
    "def chooseBestFeatureToSplit(dataSet): #选择最好的划分特征\n",
    "    numFeatures = len(dataSet[0]) - 1 #求出数据集特征总数\n",
    "    baseEntropy = calcShannonEnt(dataSet) #初始熵\n",
    "    bestInfoGain,bestFeature = 0.0,-1 #最优信息增益和最优特征\n",
    "    for i in range(numFeatures):\n",
    "        featList = [example[i] for example in dataSet]\n",
    "        uniqueVals = set(featList)\n",
    "        newEntropy = 0.0\n",
    "        for value in uniqueVals:\n",
    "            subDataSet = splitDataSet(dataSet,i,value)\n",
    "            prob = len(subDataSet)/float(len(dataSet))\n",
    "            newEntropy += prob * calcShannonEnt(subDataSet) #计算特征的熵\n",
    "        infoGain = baseEntropy - newEntropy #计算信息增益\n",
    "        if(infoGain > bestInfoGain): #找到最好的特征\n",
    "            bestInfoGain = infoGain\n",
    "            bestFeature = i\n",
    "    return bestFeature\n",
    "\n",
    "def majorityCnt(classList): #选择出现次数做多的结果\n",
    "    classCount = {}\n",
    "    for vote in classList:\n",
    "        if vote in classCount.keys():\n",
    "            classCount[vote] = 0\n",
    "        classCount[vote] += 1\n",
    "\n",
    "    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)#倒叙排序\n",
    "    return sortedClassCount[0][0] #返回第一个结果\n",
    "\n",
    "def createTree(dataSet,labels): #创建树\n",
    "    classList = [example[-1] for example in dataSet]\n",
    "    if classList.count(classList[0]) == len(classList): #如果数据集最后一列的第一个值等于整个集合的数量，则数据集只有你一个类别，直接返回\n",
    "        return classList[0]\n",
    "    if len(dataSet[0]) == 1: #使用完了所有特征，仍然不能将数据集划分为仅包含唯一类别的分组\n",
    "        return majorityCnt(classList)\n",
    "\n",
    "    bestFeat = chooseBestFeatureToSplit(dataSet) #选择最优的列\n",
    "    bestFeatLabel = labels[bestFeat] #得到最优列对应的label含义\n",
    "    myTree = {bestFeatLabel:{}}\n",
    "\n",
    "    del(labels[bestFeat])\n",
    "    featValues = [example[bestFeat] for example in dataSet]\n",
    "    uniqueVals = set(featValues)\n",
    "    for value in uniqueVals:\n",
    "        subLabels = labels[:] #求出剩余标签\n",
    "        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)\n",
    "    return myTree\n",
    "\n",
    "def classify(inputTree,featLabels,testVec): #划分输入节点\n",
    "    firstStr = inputTree.keys()[0] #获得树对应的key值\n",
    "    secondDict = inputTree[firstStr] #通过key得到根节点对应的value\n",
    "    featIndex = featLabels.index(firstStr)\n",
    "    key = testVec[featIndex]\n",
    "    valueOfFeat = secondDict[key]\n",
    "\n",
    "    if isinstance(valueOfFeat,dict):\n",
    "        classLabel = classify(valueOfFeat,featLabels,testVec)\n",
    "    else:\n",
    "        classLabel = valueOfFeat\n",
    "    return classLabel\n",
    "fr = open('lenses.txt')\n",
    "lenses = [inst.strip().split('\\t') for inst in fr.readlines()]\n",
    "lensesLabels = ['age','prescript','astigmatic','tearRate']\n",
    "lensesTree = createTree(lenses,lensesLabels)\n",
    "print(lensesTree)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
